package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         474,
		Discription: "给一个只含'0' '1'字符的字符串数组，求0的总数不超过m、1的总数不超过n的最长子集",
		Level:       3,
		Labels: map[string]int{
			"0-1背包":   1,
			"动态规划": 1,
		},
	})
}

func FindMaxForm(strs []string, m int, n int) int {
	counts := make([][2]int, len(strs))
	for i, str := range strs {
		var count [2]int
		for j := range str {
			if str[j] == '0' {
				count[0]++
			} else {
				count[1]++
			}
		}
		counts[i] = count
	}

	//dp[i][j][k]表示从counts[:i]中选出的0的总数不超过m、1的总数不超过n的最长子集的长度
	dp := make([][][]int, len(strs)+1)
	for i := range dp {
		dp[i] = make([][]int, m+1)
		for j := range dp[i] {
			dp[i][j] = make([]int, n+1)
		}
	}

	//0-1背包 完全背包的问题都是先遍历所有背包
	//然后遍历限制/奖励...
	for i := 1; i <= len(strs); i++ {
		for j := 0; j <= m; j++ {
			for k := 0; k <= n; k++ {
				if counts[i-1][0] == j && counts[i-1][1] == k {
					dp[i][j][k] = max(1, dp[i-1][j][k])
				} else if counts[i-1][0] > j || counts[i-1][1] > k {
					dp[i][j][k] = dp[i-1][j][k]
				} else {
					//dp[i-1][j][k]：不用counts[i-1]的字符串
					//dp[i-1][j-counts[i-1][0]][k-counts[i-1][1]]+1：用了counts[i-1]的字符串，注意前面要变成dp[i-1]，表示当前字符串不能二次使用
					dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-counts[i-1][0]][k-counts[i-1][1]]+1)
				}
			}
		}
	}

	return dp[len(strs)][m][n]
}